package seqlist.leetcode;

/**
 * 删除链表中所有重复元素
 */
public class Num82 {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode dummyHead = new ListNode(101);
        dummyHead.next = head;
        ListNode prev = dummyHead;
        ListNode cur = prev.next;
        while (cur != null) {
            ListNode next = cur.next;
            if (next == null) {
                return dummyHead.next;
            }else {
                // 此时链表中至少有两个节点
                if (cur.val == next.val) {
                    // cur和next重复
                    // 让next一直向后移动，直到走到第一个与cur.val不相等的节点
                    while (next != null && cur.val == next.val) {
                        next = next.next;
                    }
                    // prev - 第一个重复节点的前驱
                    // next - 最后一个重复节点的后继
                    // prev - next全是重复元素，需要删除
                    prev.next = next;
                    // prev不动，cur走到当前next继续判断后面是否还有重复元素
                    cur = next;
                }else {
                    // cur与next不重复
                    prev = prev.next;
                    cur = cur.next;
                }
            }
        }
        return dummyHead.next;
    }
}
